package Leetcode.每日一题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//https://leetcode.cn/problems/4sum/solution/yi-miao-jiu-neng-gao-dong-de-duo-ge-qiu-ya50w/
public class 多数之和 {
    public static List<List<Integer>> threeSum(int[] nums, int target) {
        List<List<Integer>> arr = new ArrayList<List<Integer>>();
        if(nums.length < 3){
            return arr;
        }
        //排序
        Arrays.sort(nums);
        if(nums[0]>target){
            return arr;
        }
        int l,r;//左右指针
        int t;
        for (int i=0; i<nums.length-2; i++){
            t = target - nums[i];
            if(i>0 && nums[i-1]==nums[i] ){
                continue;
            }
            l=i+1;//初始化左是第一个指针的右边一个
            //索引要-1  长为7  也就是nums[6]  每次循环都需要
            // 第一个指针每遍历一次  r就要回到最右边的位置
            r=nums.length-1;
            while(l<r){
                if(nums[l]+nums[r]==t){
                    //存入符合要求的值
                    arr.add(new ArrayList<>(Arrays.asList(nums[i], nums[l], nums[r])));
                    //需要注意顺序
                    while(l < r && nums[l] == nums[l+1]){
                        l++;
                    }
                    while(l < r && nums[r] == nums[r-1]){
                        r--;
                    }
                    l++;//已经是排序列表了，所以左右指针都要动一下
                    r--;
                }else if(nums[l]+nums[r]>t){
                    r--;
                }else{
                    l++;
                }
            }
        }
        return arr;
    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> arr = new ArrayList<>();
        if(nums.length < 4){
            return arr;
        }
        Arrays.sort(nums);

        for(int i = 0; i < nums.length-3; i++){
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            for(int j = i+1; j < nums.length-2; j++){
                if(j > i+1 && nums[j] == nums[j-1]){
                    continue;
                }
                int l = j+1;
                int r = nums.length-1;
                while(l < r){
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if(sum == target){
                        //存入
                        arr.add(new ArrayList<>
                                (Arrays.asList(nums[i], nums[j], nums[l], nums[r])));
                        //去重
                        while(l < r && nums[l] == nums[l+1]){
                            l++;
                        }
                        while(l < r && nums[r] == nums[r-1]){
                            r--;
                        }
                        l++;
                        r--;
                    }
                    else if(sum > target){
                        r--;
                    }
                    else{
                        l++;
                    }
                }
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] a= {1,2,5,4,3,9,-4,-6,-2};
        int target =  3;
        System.out.println(threeSum(a,target));
        System.out.println(fourSum(a,target));
    }
}
